package StackAndQueuePackage;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author Lzm
 * @version 1.0
 */
public class topKFrequent_ {

  @Test
  public void topKFrequentTest(){
    //int[] nums = new int[]{1,1,1,2,2,3,3,3,3};
    //int[] nums = new int[]{1,2,1,2,1,2,3,1,3,2};
    //int[] nums = new int[]{1,1,1,2,2,3};
    int[] nums = new int[]{-1,1,4,-4,3,5,4,-2,3,-1};
    int k = 3;
    int[] ints = topKFrequent(nums, k);
    for (int anInt : ints) {
      System.out.println(anInt);
    }
  }

  public int[] topKFrequent(int[] nums, int k) {
    // 将nums遍历出放到map中
    Map<Integer,Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      if (map.containsKey(nums[i])){
        map.put(nums[i],map.get(nums[i]) + 1);
      }
      else{
        map.put(nums[i],1);
      }
    }
    // 基于小顶堆实现
    PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[1] - o2[1];
      }
    });
    Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
    for (Map.Entry<Integer, Integer> entry : entries) {
      if (queue.size() < k){
        queue.add(new int[]{entry.getKey(),entry.getValue()});
      }
      else{
        if (entry.getValue() > queue.peek()[1]){
          queue.poll();
          queue.add(new int[]{entry.getKey(),entry.getValue()});
        }
      }
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
      if (!queue.isEmpty())
      result[i] = queue.peek()[0];
    }
    return result;
  }
}
